// Count Sort.cpp : The count sort algorithm described in book only supports input ranging from 0 to n.
//                  While through improvement, this program supports negative input.

#include "stdafx.h"
#include <iostream>
#include <vector>

using namespace std;

pair<int,int> get_min_max( vector<int> &orig ) {
	int temp1 = orig[0];
	int temp2 = orig[0];
	for ( vector<int>::iterator ivec = orig.begin(); ivec != orig.end(); ++ ivec ) {
		if ( *ivec < temp1 )
			temp1 = *ivec;
		if ( *ivec > temp2 )
			temp2 = *ivec;
	}
	return make_pair(temp1,temp2);
}


void Counting_Sort( vector<int> &orig, vector<int> &final, int mini, int maxi) {
	int shift = 0;
	if ( mini < 0 ) {
		maxi -= mini;
		shift = 0 - mini + 1;
	}
	if ( mini > 0 )
		mini = 0;
	vector<int> C(maxi+1);
	for ( vector<int>::iterator ivec = orig.begin(); ivec != orig.end(); ++ ivec )
		C[*ivec-1+shift] ++;
	for ( vector<int>::iterator ivec_c = C.begin(); ivec_c != (C.end()-1); ++ ivec_c )
		(*(ivec_c+1)) += *ivec_c;
	for ( vector<int>::iterator ivec_o = orig.begin(); ivec_o != orig.end(); ++ ivec_o ) {
		final[C[*ivec_o+shift-1]-1] = *ivec_o;
		-- C[*ivec_o+shift-1];
	}
}

int _tmain()
{
	int buffer;
	pair<int,int> min_max;
	vector<int> A;
	cout << "please input an array of numbers." << endl;
	while( cin >> buffer)
		A.push_back(buffer);
	min_max = get_min_max(A);
	vector<int> B(A.size());
	Counting_Sort(A,B,min_max.first,min_max.second);
	for ( vector<int>::iterator ivec_b = B.begin(); ivec_b != B.end(); ++ ivec_b )
		cout << *ivec_b << "\t";
	cout << endl;
	return 0;
}

